package com.lsa.edmonds.chap10;

import java.util.List;

import com.lsa.helpers.Utils;
import com.lsa.shenn.common.Sorter;

public class HeapSort implements Sorter {

	@Override
	public int[] sort(int[] array) {
		int n = array.length;
		if (n < 2) return array;
		
		makeHeap2(1, array);
		
		for (int i = n; i > 0; i--) {
			Utils.swap(array, 0, i - 1);
			heapify(1, array, i - 1);
		}
		
		return array;
	}

	@Override
	public List<Integer> sort(List<Integer> array) {
		throw new IllegalArgumentException();
	}
	
	public static void heapify(int rootIndex, int[] array, int length) {
		int rootElement = array[rootIndex - 1];
		Integer leftSubtreeRootElement = getLeftSubtree(rootIndex, array, length);
		Integer rightSubtreeRootElement = getRightSubtree(rootIndex, array, length);
		
		if (leftSubtreeRootElement == null && rightSubtreeRootElement == null){
			return;
		}
		
		if ( rightSubtreeRootElement == null){
			if (rootElement < leftSubtreeRootElement){
				swapWithSubtree(rootIndex, rootIndex * 2, array);
			}
			heapify(rootIndex * 2, array, length);
			return;
		}
		
		int maxSubtreeIndex = maxSubtreeIndex(rootIndex, array);
		if (array[maxSubtreeIndex - 1] > rootElement){
			swapWithSubtree(rootIndex, maxSubtreeIndex, array);
			heapify(maxSubtreeIndex, array, length);
		}
	}
	
	public static void makeHeap(int rootIndex, int[] array) {
		if (rootIndex > array.length / 2) return; // it is a leaf or 'nothing' node
		
		makeHeap(rootIndex * 2, array);
		makeHeap(rootIndex * 2 + 1, array);
		heapify(rootIndex, array, array.length);
	}
	
	public static void makeHeap2(int rootIndex, int[] array) {
		if (rootIndex > array.length / 2) return; // it is a leaf or 'nothing' node
		
		for(int k = array.length / 2; k > 0; --k){
			heapify(k, array, array.length);
		}
	}
	
	private static int maxSubtreeIndex(int root, int[] array){
		int leftSubtreeIndex = root * 2 - 1;
		int rightSubtreeIndex = root * 2 + 1 - 1;
		
		if (array[leftSubtreeIndex] < array[rightSubtreeIndex]) return rightSubtreeIndex + 1;
		
		return leftSubtreeIndex + 1;
	}
	
	private static void swapWithSubtree(int root, int subtreeRootIndex, int[] array){
		int rootElement = array[root - 1];
		array[root - 1] = array[subtreeRootIndex - 1];
		array[subtreeRootIndex - 1] = rootElement;
	}
	
	private static Integer getLeftSubtree(int root, int[] array, int length){
		int subtreeRootIndex = root * 2;
		if (subtreeRootIndex > length ){
			return null;
		}
		
		return array[subtreeRootIndex - 1];
	}
	
	private static Integer getRightSubtree(int root, int[] array, int length){
		int subtreeRootIndex = root * 2 + 1;
		if (subtreeRootIndex > length ){
			return null;
		}
		
		return array[subtreeRootIndex - 1];
	}
}
